Klawiatura

Limit pamięci: 32 MB

Bajtazar dostał w prezencie niezwykłą klawiaturę. Jest na niej klawiszy ustawionych w wierszach po kolumn. Co więcej wszystkie klawisze oprócz tego w lewym górnym rogu są przykryte kostkami domina o wymiarach , łącznie jest zatem kostek domina. Bajtazar może wykonywać ruchy polegające na przesunięciu na odkryte pole jednej z kostek sąsiadujących z nim krótszym bokiem. Może też naciskać klawisze, o ile nie są one przykryte.

Bajtazar chciałby przetestować (tj. nacisnąć) wszystkie klawisze z samogłoskami, czyli literami a, e, i, o, u i y. Ilu co najmniej przesunięć potrzebuje, żeby tego dokonać?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby i () - wymiary klawiatury. Kolejne wierszy zawiera po małych liter alfabetu angielskiego, które opisują poszczególne wiersze klawiatury. W następnych wierszach znajduje się po znaków opisujących ułożenie kostek domina: . (kod ASCII 46) oznacza klawisz niezakryty, - (kod ASCII 45) oznacza klawisz zakryty kostką ustawioną poziomo, zaś | (kod ASCII 124) - klawisz zakryty kostką ustawioną pionowo.

Wyjście

Jeśli Bajtazar nie jest w stanie nacisnąć wszystkich klawiszy z samogłoskami, na standardowe wyjście wypisz słowo NIE. W przeciwnym przypadku należy wypisać minimalną liczbę przesunięć, jakie musi wykonać Bajtazar, aby nacisnąć wszystkie klawisze z samogłoskami.

Przykład

Dla danych wejściowych:

3 3
ytr
hgf
dsa
.--
|||
|||

poprawną odpowiedzią jest:

2

Autor zadania: Jakub Pachocki.